// // 两两交换链表中的节点
// https://leetcode.cn/problems/swap-nodes-in-pairs/description/?envType=study-plan-v2&envId=top-100-liked
// /**
//  * Definition for singly-linked list.
//  * struct ListNode {
//  *     int val;
//  *     ListNode *next;
//  *     ListNode() : val(0), next(nullptr) {}
//  *     ListNode(int x) : val(x), next(nullptr) {}
//  *     ListNode(int x, ListNode *next) : val(x), next(next) {}
//  * };
//  */
// class Solution {
// public:
//     ListNode* swapPairs(ListNode* head) {
//         //引入一个哨兵节点
//         ListNode* newnode =new ListNode(0);
//         newnode->next = head;
//         ListNode* before =newnode;
//         ListNode* cur = head;
//         while(cur !=nullptr)
//         {
//             //我们现在需要做的是，交换两个节点的位置，然后把第一个的节点，链接到交换完后的节点
//             if(cur->next ==nullptr)
//             {
//                 return newnode->next;
//             }
//             ListNode* next = cur->next;
//             ListNode* nnext =next->next;
//             cur->next =nnext;
//             before->next =next;
//             before->next->next =cur;
//             before = cur;
//             cur = nnext;
//         }
//         return newnode->next;
        
//     }
// };


// https://leetcode.cn/problems/reorder-list/
// /**
//  * Definition for singly-linked list.
//  * struct ListNode {
//  *     int val;
//  *     ListNode *next;
//  *     ListNode() : val(0), next(nullptr) {}
//  *     ListNode(int x) : val(x), next(nullptr) {}
//  *     ListNode(int x, ListNode *next) : val(x), next(next) {}
//  * };
//  */
// class Solution {
// public:
//     void reorderList(ListNode* head) {
//         // 通过观察可以只想相当于把链表后半部分逆置，然后把两个链表合并成一个链表
//         // 第一步先找到中间节点
//         ListNode* slow = head;
//         ListNode* fast = head;
//         while (fast && fast->next) {
//             slow = slow->next;
//             fast = fast->next->next;
//         }
//         // 第二步 逆置节点
//         ListNode* NewList = new ListNode(0); // 虚拟头节点
//         ListNode* cur = slow->next;
//         slow->next = nullptr; // 因为是浅拷贝，所以这里相当于直接分成了两个子串
//         while (cur) {
//             ListNode* next = cur->next;
//             cur->next = NewList->next;
//             NewList->next = cur;
//             cur = next;
//         }
//         // 第三步合并两个链表
//         ListNode* ret = new ListNode(0);
//         ListNode* Cur = ret;
//         ListNode* cur1 = head;
//         ListNode* cur2 = NewList->next;
//         while (cur1) {
//             Cur->next = cur1;
//             cur1 = cur1->next;
//             Cur = Cur->next;
//             if (cur2) {
//                 Cur->next = cur2;
//                 Cur = Cur->next;
//                 cur2 = cur2->next;
//             }
//         }
//         head = ret->next;
//     }
// };